import java.util.*;

public class Test {

    public List<String> topKFrequent(String[] words, int k) {
        //1.统计每个单词出现的次数
        Map<String,Integer> map=new HashMap<>();
        for(String word: words){
            if(map.get(word)==null){
                map.put(word,1);
            }else{
                int val=map.get(word);
                map.put(word,val+1);
            }
        }
        //遍历map,获取每个单词的频率,存放在小根堆里 TOPK 问题
        //创建小根堆  默认根据频率
        PriorityQueue<Map.Entry<String,Integer> > minHeap=new PriorityQueue<>(new Comparator<Map.Entry<String, Integer>>() {
            @Override
            public int compare(Map.Entry<String, Integer> o1, Map.Entry<String, Integer> o2) {
                if(o1.getValue().compareTo(o2.getValue())==0){
                    return o2.getKey().compareTo(o1.getKey());
                }
                return o1.getValue().compareTo(o2.getValue());
            }
        });

        for(Map.Entry<String,Integer> entry:map.entrySet()){
            if(minHeap.size()<k){
                minHeap.offer(entry);
            }else{
                Map.Entry<String,Integer> top=minHeap.peek();

                //频率相同
                if(top.getValue().compareTo(entry.getValue())==0){
                    if(top.getKey().compareTo(entry.getKey())>0){
                        //堆顶def_3,entry 是abs_3 出堆
                        minHeap.poll();
                        minHeap.offer(entry);
                    }
                }else{
                    //频率不相同
                    //堆顶def_3,entry 是abs_6 出堆
                    if(entry.getValue().compareTo(top.getValue())>0){
                        minHeap.poll();
                        minHeap.offer(entry);
                    }
                    //堆顶def_3,entry 是abs_2 不动
                }
            }
        }
        List<String> ret=new ArrayList<>();
        for (int i = 0; i < k; i++) {
            Map.Entry<String,Integer> tmp=minHeap.poll();
            ret.add(tmp.getKey());
        }
        Collections.reverse(ret);//逆置
        return ret;
    }

    public static void main(String[] args) {
        //找出10w个数据中, 第一个重复的值
        int[] array={1,3,2,1,4,3,1,45,3};
        HashSet<Integer> set=new HashSet<>();
        for(int x:array){
            if(!set.contains(x)){
                set.add(x);
            }else{
                System.out.println(x);
                return;
            }
        }
        //给你10W个数据,把这些数据去重
/*        int[] array={1,3,2,1,4,3,1,45,3};
        HashSet<Integer> set2=new HashSet<>();
        for(int x:array){
            set2.add(x);//set天然去重
        }
        System.out.println(set2);*/

/*
        //统计10W个数据,重复数据出现的次数  必须使用map
        int[] array={1,3,2,1,4,3,1,45,3};
        Map<Integer,Integer> map=new HashMap<>();
        for (int i = 0; i < array.length; i++) {
            if(map.get(array[i])==null){
                map.put(array[i],1);//没存储过的值 ,出现次数设为1
            }else{
                int val=map.get(array[i]);
                map.put(array[i],val+1);
            }
        }
        for(Map.Entry<Integer,Integer> entry:map.entrySet()){
            System.out.println("数字:"+entry.getKey()+"次数:"+entry.getValue());
        }*/

    }


    public int numJewelsInStones(String jewels, String stones) {
        HashSet<Character> set=new HashSet<>();
        int count=0;
        for(int i=0;i<jewels.length();i++){
            char ch=jewels.charAt(i);
            set.add(ch);
        }
        for(int i=0;i<stones.length();i++){
            char ch=stones.charAt(i);
            if(set.contains(ch)){
                count++;
            }
        }
        return count;
    }

//随即表的复制
/*    public Node copyRandomList(Node head) {
        HashMap<Node,Node> map=new HashMap<>();
        //第一次遍历链表
        Node cur =head;
        while(cur != null){
            Node node=new Node(cur.val);
            map.put(cur,node);
            cur=cur.next;
        }

        //第二次遍历链表
        cur=head;
        while(cur!=null){
            map.get(cur).next=map.get(cur.next);
            map.get(cur).random=map.get(cur.random);
            cur=cur.next;
        }
        return map.get(head);
    }*/
        //寻找出现一个的数字
    public int singleNumber(int[] nums) {
        HashSet<Integer> hashSet=new HashSet<>();
        for (int i = 0; i < nums.length; i++) {
            if(!hashSet.contains(nums[i])){
                hashSet.add(nums[i]);
            }else{
                hashSet.remove(nums[i]);
            }
        }
        for (int i = 0; i < nums.length; i++) {
            if (hashSet.contains(nums[i])) {
                return nums[i];
            }
        }
        return -1;
    }


    public static void main22(String[] args) {

    }

    public static void main11(String[] args) {
        HashBuck hashBuck=new HashBuck();
        hashBuck.put(1,11);
        hashBuck.put(4,2424);
        hashBuck.put(14,44);
        hashBuck.put(24,1414);
        hashBuck.put(3,33);
        hashBuck.put(7,33);
        hashBuck.put(8,33);
        hashBuck.put(9,33);
        System.out.println(hashBuck.get(14));
    }
    public static void main2(String[] args) {
        Set<String> set=new TreeSet<>();
        set.add("abc");
        set.add("hello");
        set.add("abc");
        System.out.println(set);
    }
    public static void main1(String[] args) {
        BinarySearchTree bt=new BinarySearchTree();
        bt.insert(10);
        bt.insert(5);
        bt.insert(19);
        bt.insert(6);

        System.out.println(bt.search(5).val);
    }

    public static void main33(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        while (in.hasNextLine()) { // 注意 while 处理多个 case
            String str1 = in.nextLine();
            String str2 = in.nextLine();
            func(str1,str2);
        }
    }
    public static void func(String str1,String str2) {
        HashSet<Character> set = new HashSet<>();
        HashSet<Character> setBroken = new HashSet<>();
        //将str2变成大写,并以数组的形式输出
        for (char ch : str2.toUpperCase().toCharArray()) {
            set.add(ch);
        }
        for (char ch : str1.toUpperCase().toCharArray()) {
            if (!set.contains(ch) && !setBroken.contains(ch)) {
                System.out.print(ch);
                setBroken.add(ch);
            }
        }
    }
}
